package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0;i< nums.length;i++){
            if(nums[i]>0) return res;
            if(i>0&&nums[i] == nums[i-1]) continue;

            int l = i+1;
            int r = nums.length-1;
            while (l<r){
                if(nums[i]+nums[l]+nums[r] == 0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));

                    while (l+1< r&&nums[l] == nums[l+1]) l++;
                    l++;

                    while (r-1>l&&nums[r] == nums[r-1]) r--;
                    r--;

                } else if (nums[i]+nums[l]+nums[r] > 0) {
                    r--;

                }else {//<0
                    l++;
                }
            }

        }

        return res;
    }

    public static void main(String[] args) {
        new Q15().threeSum(new int[]{0,0,0});
    }
}
